package leetcode.t6Tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author K
 * @date 2024/1/30 9:18
 */
public class T95_GenerateTrees {

    /**
     * 95. 不同的二叉搜索树 II
     */
    public static List<TreeNode> generateTrees(int n) {
        return generateTree(1, n);
    }

    public static List<TreeNode> generateTree(int start, int end) {
        List<TreeNode> allTreeList = new ArrayList<>();
        if (start > end) {
            allTreeList.add(null);
            return allTreeList;
        }

        for (int i = start; i <= end; i++) {
            List<TreeNode> leftTreeList = generateTree(start, i-1);
            List<TreeNode> rightTreeList = generateTree(i+1, end);

            for (TreeNode left : leftTreeList) {
                for (TreeNode right : rightTreeList) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    allTreeList.add(root);
                }
            }

        }
        return allTreeList;
    }

    public static void main(String[] args) {
        List<TreeNode> treeNodes = generateTrees(3);
        System.out.println();
    }

}
